package puzzle.projecteuler.p100;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.net.URL;
import java.net.URLDecoder;
import java.util.ArrayList;
import java.util.List;

public class Problem096C {

	/**
	 * @param args
	 */
	public static void main(String[] args) throws Exception {
		
		long s = System.currentTimeMillis();
		int sum = 0;
		SuDoku[] sudokus = readData();
		for (SuDoku su : sudokus) {
			SuDoku r = SuDoku.solve(su);
			if (!r.isOver()) {
				throw new RuntimeException("ERROR");
			}
			System.out.println(r);
			sum += r.m[0][0]*100 + r.m[0][1]*10 + r.m[0][2];
		}
		System.out.println(sum);
		System.out.println((System.currentTimeMillis()-s) + " ms");
	}
	
	private static class SuDoku implements Cloneable {
		
		int[][] m;

		public SuDoku(int[][] m) {
			
			this.m = m;
		}
		
		public SuDoku clone() {

			int[][] x = new int[9][];
			for (int i = 0; i < 9; i ++) {
				x[i] = new int[9];
				for (int j = 0; j < 9; j ++) {
					x[i][j] = this.m[i][j];
				}
			}
			
			return new SuDoku(x);
		}
		
		public String toString() {

			StringBuffer sb = new StringBuffer();
			for (int i = 0; i < 9; i ++) {
				for (int j = 0; j < 9; j ++) {
					if (m[i][j] == 0) {
						sb.append("-").append(" ");
					} else {
						sb.append(m[i][j]).append(" ");
					}
				}
				sb.append("\n");
			}
			return sb.toString();
		}
		
		private boolean isOver() { 
			
			for (int i = 0; i < 9; i ++) {
				for (int j = 0; j < 9; j ++) {
					if (this.m[i][j] == 0) {
						return false;
					}
				}
			}
			return true;
		}
		
		private void update() {
			
			List<Integer> vs = null;
			for (int k = 0; k < 81; k ++) {
				for (int i = 0; i < 9; i ++) {
					for (int j = 0; j < 9; j ++) {
						if (this.m[i][j] == 0) {
							vs = candidates(i, j);
							if (vs.size() == 1) {
								this.m[i][j] = vs.get(0);
//								System.out.println((i+1) + ", " + (j+1) + ":" + vs.get(0));
							}
						}
					}
				}
			}
		}
		
		/**
		 * 递归求解
		 * 为了提高效率，在处理前，先调用函数update()，可有效减少递归的深度
		 * @param s
		 * @return
		 */
		public static SuDoku solve(SuDoku s) {

			s.update();
//			System.out.println(s);
			if (s.isOver()) return s;
			
			boolean found = false;
			int k = -1, m = -1;
			List<Integer> vs = null;
			for (k = 0; k < 9; k ++) {
				for (m = 0; m < 9; m ++) {
					if (s.m[k][m] == 0) {
						vs = s.candidates(k, m);
						if (vs.size() > 1) {
							found = true;
							break;
						} else if (vs.size() == 0) {
							return null;
						}
					}
				}
				if (found) break;
			}
			
			if (found) {
				for (Integer v: vs) {
					SuDoku ns = s.clone();
					ns.m[k][m] = v;
					
//					System.out.println((k+1) + ", " + (m+1) + ":" + v);
					SuDoku ss = solve(ns);
					if (ss != null && ss.isOver()) return ss;
				}
			}
			
			return null;
		}

		
		/**
		 * m[i][j]的候选数
		 * @param i
		 * @param j
		 * @return
		 */
		private List<Integer> candidates(int i, int j) {
			
			boolean[] bs = new boolean[10];
			for (int k = 0; k < 10; k ++) bs[k] = true;
			//row
			for (int k = 0; k < 9; k ++) {
				if (k != j && m[i][k] != 0) bs[m[i][k]] = false;
			}
			//column
			for (int k = 0; k < 9; k ++) {
				if (k != i && m[k][j] != 0) bs[m[k][j]] = false;
			}
			//block
			int x = i/3;
			int y = j/3;
			for (int k = 0; k < 3; k ++) {
				for (int n = 0; n < 3; n ++) {
					int s = 3*x + k;
					int t = 3*y + n;
					if ((s != i || t != j) && m[s][t] != 0) {
						bs[m[s][t]] = false;
					}
				}
			}
			
			//return
			List<Integer> list = new ArrayList<Integer>();
			for (int k = 1; k < 10; k ++) {
				if (bs[k]) {
					list.add(k);
				}
			}
			return list;
		}
	}

	public static SuDoku[] readData() throws IOException {

		URL url = Problem096C.class.getResource("Problem096.txt");
		File file = new File(URLDecoder.decode(url.getPath(), "UTF-8"));

		List<SuDoku> sudokus = new ArrayList<SuDoku>();
		BufferedReader br = new BufferedReader(new FileReader(file));
		String line = null;
		while ((line = br.readLine()) != null) {
			if (line.startsWith("Grid")) {
				int[][] m = new int[9][];
				for (int i = 0; i < 9; i ++) {
					char[] cs = br.readLine().toCharArray();
					m[i] = new int[9];
					for (int j = 0; j < 9; j ++) {
						m[i][j] = cs[j] - '0';
					}
				}
				sudokus.add(new SuDoku(m));
			}
		}
		br.close();
		return sudokus.toArray(new SuDoku[sudokus.size()]);
	}
}
